#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "DuLinkList.c"

#define NEG_NUM 1
#define POS_NUM 0
#define ADD 0
#define SUB 1
#define MUL 2
#define DIV 3
#define BASE 10

typedef struct{
	LinkList x;
	int mark;
	int len;
}LongInt;

//初始化的到一个长整数

Status InitLongInt(LongInt* c,ElemSet* str,int len){
	if(str==NULL || len==0){
		InitList(&c->x,NULL,0);
		return FAILURE;
	}
	int pos=((str[0]=='-')?1:0);
	c->mark=((str[0]=='-')?NEG_NUM:POS_NUM);
	c->len=(c->mark==NEG_NUM?len-1:len);
	InitList(&c->x,NULL,0);
	ElemSet carry,d;
	carry=0;
	for(int i=len-1;i>=pos;i--) {
		d=str[i]-'0'+carry;
		d %= BASE;
		carry=d / BASE;
		//if (carry==0) continue;
		ListInsert(c->x,1,d);
	}
	return OK;
}

Status DestroyLongInt(LongInt *a){
	a->len=0;
	if(a->x==NULL) return SUCCESS;
	DestoryList(a->x);
	return SUCCESS;
}

//比较两个长整数的绝对值大小，前者小返回负数，相等返回 0 ,前者大返回正数
int compareLongInt(LongInt a1,LongInt a2){
	if(a1.len==a2.len){
		int sign=compearList(a1.x,a2.x);
		if(sign>0) return 1;
		else if(sign==0) return 0;
		else return -1;
	}
	else if(a1.len>a2.len) return 1;
	else return -1;
}

//获取当前操作位的值
ElemSet getCurBit(LongInt a,int i){
	ElemSet e;
	int len=ListLength(a.x);
	GetElem(a.x,len+1-i,&e);
	return e;
}

//输出长整数类型
void printLongInt(LongInt la){
	if(la.x->next==NULL) return;
	char str[100];
	ToString(la.x,str);
	if(la.mark==NEG_NUM) printf("-%s\n",str);
	else printf("%s\n",str);
}

void sub(LongInt a,LongInt b,LongInt* c){
	LinkList p,q,r;
	p=getTail(a.x);
	q=getTail(b.x);
	r=c->x;
	ElemSet e,carry_bit=0,borrow_bit=0;
	while(p!=a.x && q!=b.x){
		carry_bit=e=p->data+10+carry_bit-q->data-borrow_bit;
		e=e%10;
		ListInsert(r,1,e);
		c->len++;
		carry_bit=carry_bit/10;
		borrow_bit=1;
		p=p->prior;
		q=q->prior;
	}
	while(p!=a.x){
		carry_bit=e=p->data+10+carry_bit-borrow_bit;
		e=e%10;
		carry_bit=carry_bit/10;
		ListInsert(r,1,e);
		c->len++;
		borrow_bit=0;
		p=p->prior;
	}
}

void add(LongInt a,LongInt b,LongInt *c) {
	LinkList p,q,r;
	p=getTail(a.x);
	q=getTail(b.x);
	r=c->x;
	ElemSet e,carry_bit=0;
	while(p!=a.x && q!=b.x) {
		carry_bit=e=p->data+q->data+carry_bit;
		e=e%10;
		carry_bit=carry_bit/10;
		ListInsert(r,1,e);
		c->len++;
		p=p->prior;
		q=q->prior;
	}
	LinkList s;
	if(p==a.x) s=q;
	else s=p;
	while (!(s==a.x || s==b.x)) {
		carry_bit=e=s->data+carry_bit;
		e=e%10;
		carry_bit=carry_bit/10;
		ListInsert(r,1,e);
		c->len++;
		s=s->prior;
	}
}

void add2(LongInt* a,LongInt* b){
	printLongInt(*a);
	printLongInt(*b);
	LinkList p,q;
	int st=(a->len>b->len?a->len:b->len)+1,i=0;
	char* str=(char*)malloc(st*sizeof(char));
	p=getTail(a->x);
	q=getTail(b->x);
	ElemSet e,carry_bit=0;
	printf("***********\n");
	while(p!=a->x && q!=b->x) {
		carry_bit=e=p->data+q->data+carry_bit;
		e=e%10;
		carry_bit=carry_bit/10;
		str[i++]=e;
		p=p->prior;
		q=q->prior;
	}
	LinkList s;
	if(p==a->x) s=q;
	else s=p;
	while (!(s==a->x || s==b->x)) {
		carry_bit=e=s->data+carry_bit;
		e=e%10;
		carry_bit=carry_bit/10;
		str[i++]=e;
		s=s->prior;
	}
	if(carry_bit!=0) str[i]=carry_bit;
	else st--;
	ClearList(a->x);
	FillList(a->x,str,st);
	a->len=st;
	free(str);
}

void addition(LongInt a,LongInt b,LongInt* c) {
	InitList(&c->x,NULL,0);
	int x=a.mark ^ b.mark;
	if (x==0){
		add(a,b,c);
		c->mark=a.mark;
	} 
	else {
		int y=compareLongInt(a,b);
		if (y==0) {
			ListInsert(c->x,1,0);	
			return ;
		}
		else if (y>0){
			sub(a,b,c);
			c->mark=a.mark;
		}  else {
			sub(b,a,c);
			c->mark=b.mark;
		}
	}
}

void subtration(LongInt a,LongInt b,LongInt* c){
	InitList(&c->x,NULL,0);
	int s=compareLongInt(a,b);
	if(a.mark==POS_NUM && b.mark==NEG_NUM) add(a,b,c);
	else if(a.mark==NEG_NUM && b.mark==POS_NUM){add(a,b,c);c->mark=NEG_NUM;}

	else if(s>0 && a.mark==POS_NUM && b.mark==POS_NUM) sub(a,b,c);
	else if(s>0 && a.mark==NEG_NUM && b.mark==NEG_NUM){sub(a,b,c);c->mark=NEG_NUM;}
	else if(s<0 && a.mark==NEG_NUM && b.mark==NEG_NUM) sub(b,a,c);
	else if(s<0 && a.mark==POS_NUM && b.mark==POS_NUM) {sub(b,a,c);c->mark=NEG_NUM;}

}

void bit_mul(LongInt a,ElemSet e,LongInt* c){
	LinkList p=getTail(a.x),r=c->x;
	ElemSet res,carry_bit=0;
	while(p->prior!=NULL){
		carry_bit=res=p->data*e+carry_bit;
		res=res%10;
		carry_bit=carry_bit/10;
		ListInsert(r,1,res);
		c->len++;
		p=p->prior;
	}
	if(carry_bit!=0){
		ListInsert(r,1,carry_bit);
		c->len++;
	}
}

void mul(LongInt la,LongInt lb,LongInt* res){
	LongInt c;
	InitList(&res->x,NULL,0);
	InitList(&c.x,NULL,0);
	c.len=0;
	res->len=0;
	int i=0,j=0;
	LinkList p=getTail(la.x);
	while(p!=la.x){
		for(i=j;i>0;i--){
			ListInsert(c.x,1,0);
			c.len++;
		}
		bit_mul(lb,p->data,&c);
		add2(res,&c);
		ClearList(c.x);
		c.len=0;
		p=p->prior;
		j++;
	}
	DestroyLongInt(&c);
}

int division(LongInt* la,LongInt* lb,LongInt* c){
	return 0;
}

